// Binary heap implementation from:
// http://eloquentjavascript.net/appendix2.html
function BinaryHeap(scoreFunction) {"use strict";
	this.content = [];
	this.scoreFunction = scoreFunction;
}

//Adds new element
BinaryHeap.prototype.push = function(bhElement) {"use strict";
	// Add the new element to the end of the array.
	this.content.push(bhElement);
	// Allow it to bubble up.
	this.bubbleUp(this.content.length - 1);
};

//Removes best element according to the scoringFunction.
//For instance, if scoringFunction=-distance, the father, the smaller(the better). Therefore, farthest element is removed.
BinaryHeap.prototype.pop = function() {"use strict";
	var result, end;
	// Store the first element so we can return it later.
	result = this.content[0];
	// Get the element at the end of the array.
	end = this.content.pop();
	// If there are any elements left, put the end element at the
	// start, and let it sink down.
	if (this.content.length > 0) {
		this.content[0] = end;
		this.sinkDown(0);
	}
	return result;
};

//Returns best element according to the scoringFunction.
BinaryHeap.prototype.peek = function() {"use strict";
	return this.content[0];
};

BinaryHeap.prototype.remove = function(bhElement) {"use strict";
	var len, i, end;
	len = this.content.length;
	// To remove a value, we must search through the array to find it.
	for ( i = 0; i < len; i = i + 1) {
		if (this.content[i] === bhElement) {
			// When it is found, the process seen in 'pop' is repeated
			// to fill up the hole.
			end = this.content.pop();
			if (i !== len - 1) {
				this.content[i] = end;
				if (this.scoreFunction(end) < this.scoreFunction(bhElement)) {
					this.bubbleUp(i);
				} else {
					this.sinkDown(i);
				}
			}
			return;
		}
	}
	throw new Error("Node not found.");
};

BinaryHeap.prototype.size = function() {"use strict";
	return this.content.length;
};

// Takes value at n-th position and moves it towards the root of the tree 
// (making sure n-th value is now sorted)
BinaryHeap.prototype.bubbleUp = function(pos) {"use strict";
	var element, parentN, parent;
	// Fetch the element that has to be moved.
	element = this.content[pos];
	// When at 0, an element can not go up any further.
	while (pos > 0) {
		// Compute the parent element's index, and fetch it.
		parentN = Math.floor((pos + 1) / 2) - 1;
		parent = this.content[parentN];
		// Swap the elements if the parent is greater.
		if (this.scoreFunction(element) < this.scoreFunction(parent)) {
			this.content[parentN] = element;
			this.content[pos] = parent;
			// Update 'n' to continue at the new position.
			pos = parentN;
		} else {
			// Found a parent that is less, no need to move it further.
			break;
		}
	}
};

// Takes value at n-th position and moves it downwards (further from the root of the tree)
// (making sure n-th value is now sorted)
BinaryHeap.prototype.sinkDown = function(pos) {"use strict";
	var length, element, elemScore, child2N, child1N, swap, child1, child2, child1Score, child2Score;
	// Look up the target element and its score.
	length = this.content.length;
	element = this.content[pos];
	elemScore = this.scoreFunction(element);
	while (true) {
		// Compute the indices of the child elements.
		child2N = (pos + 1) * 2;
		child1N = child2N - 1;
		// This is used to store the new position of the element,
		// if any.
		swap = null;
		// If the first child exists (is inside the array)...
		if (child1N < length) {
			// Look it up and compute its score.
			child1 = this.content[child1N];
			child1Score = this.scoreFunction(child1);
			// If the score is less than our element's, we need to swap.
			if (child1Score < elemScore) {
				swap = child1N;
			}
		}
		// Do the same checks for the other child.
		if (child2N < length) {
			child2 = this.content[child2N];
			child2Score = this.scoreFunction(child2);
			if (child2Score < (swap === null ? elemScore : child1Score)) {
				swap = child2N;
			}
		}
		// If the element needs to be moved, swap it, and continue.
		if (swap !== null) {
			this.content[pos] = this.content[swap];
			this.content[swap] = element;
			pos = swap;
		} else {
			// Otherwise, we are done.
			break;
		}
	}
};
